package com.kehao.newcoder;

import com.kehao.utils.LeetCodeUtil;
import org.junit.Test;

import java.util.HashSet;

public class NCSolution109 {


    /**
     * 并查集
     *
     * @param grid
     * @return
     */
    public int solve1(char[][] grid) {
        int height = grid.length;
        int width = grid[0].length;
        Node[][] nodeSet = new Node[height][width];
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                if (grid[i][j] == 1) {
                    nodeSet[i][j] = new Node();
                    if (i > 0 && grid[i - 1][j] == 1) {
                        combine(nodeSet[i][j], nodeSet[i - 1][j]);
                    }
                    if (j > 0 && grid[i][j - 1] == 1) {
                        combine(nodeSet[i][j], nodeSet[i][j - 1]);
                    }
                }
            }
        }
        HashSet<Node> hashSet = new HashSet();
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                if (grid[i][j] == 1) {
                    Node parent = findParent(nodeSet[i][j]);
                    hashSet.add(parent);
                }
            }
        }
        return hashSet.size();
    }

    class Node {
        Node parent;
    }

    public void combine(Node node1, Node node2) {
        Node node1Parent = findParent(node1);
        Node node2Parent = findParent(node2);
        if (node1Parent != node2Parent) {
            node1Parent.parent = node2Parent;
        }
    }

    private Node findParent(Node node1) {
        Node parent = node1;
        while (parent.parent != null) {
            parent = parent.parent;
        }
        node1.parent = parent != node1 ? parent : null;
        return parent;
    }


    /**
     * 深度优先搜索
     */
    public int solve2(char[][] grid) {
        int height = grid.length;
        int width = grid[0].length;
        int result = 0;
        int[][] visited = new int[height][width];
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                if(grid[i][j] == 1 && visited[i][j]==0){
                    result++;
                }
                dfs(grid, visited,i,j);
            }
        }
        return result;
    }

    private void dfs(char[][] grid, int[][] visited, int i, int j) {
        if(visited[i][j]==1||grid[i][j]==0){
            return;
        }
        visited[i][j]=1;
        if(i>0) dfs(grid,visited,i-1,j);
        if(i<grid.length-1)dfs(grid,visited,i+1,j);
        if(j>0) dfs(grid,visited,i,j-1);
        if(j<grid.length-1)dfs(grid,visited,i,j+1);
    }

    @Test
    public void test() {
        System.out.println(LeetCodeUtil.bracketTransform("[[1,1,0,0,0],[0,1,0,1,1],[0,0,0,1,1],[0,0,0,0,0],[0,0,1,1,1]]"));
    }

    @Test
    public void test01() {
        char[][] grid = {{1, 1, 0, 0, 0}, {0, 1, 0, 1, 1}, {0, 0, 0, 1, 1}, {0, 0, 0, 0, 0}, {0, 0, 1, 1, 1}};
        System.out.println(solve2(grid));
    }

    @Test
    public void test02() {
        char[][] grid = {{1}};
        System.out.println(solve2(grid));
    }
}
